package com.zhongge.heap;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @ClassName TopK
 * @Description TODO 堆的应用==》toPk问题
 * @Author zhongge
 * @Date 2025/9/7 13:26
 * @Version 1.0
 */

class ImplMaxHeapConstructor implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        //比较对象都是用他（逆着大堆）
        return o2.compareTo(o1);
    }
}
class ImplMinHeapConstructor implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        //比较对象都是用他(顺着小堆)==》因为PriorityQueue底层就是小堆
        return o1.compareTo(o2);
    }
}
public class TopK {
    /**
     * 堆的应用：最小k个数
     * @param arr 原数组
     * @param k 指定数的个数
     * @return 返回所指定的前k个数
     */
    public int[] smallestK(int[] arr, int k) {
        int[] ints = new int[k];
        if (arr == null || k <= 0) {
            return ints;
        }
        //首先创建比较器
        ImplMaxHeapConstructor implMaxHeapConstructor = new ImplMaxHeapConstructor();
        //创建优先级队列的对象
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(implMaxHeapConstructor);
        //将前k个元素进行大根堆
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //比较
        for (int i = k; i < arr.length; i++) {
            int peek = priorityQueue.peek();
            if (arr[i] < peek){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ints[i] = priorityQueue.poll();
        }
        return ints;
    }
}
